
#include "config.h"

node_t *CreateLinkList(void)
{
	node_t *head;

	head = malloc(sizeof(node_t));
	if (head == NULL)
		return head;

	memset(head, 0, sizeof(node_t));
	head->next = NULL;

	return head;
}

// 在指定位置插入
int InsertLinkList(node_t *head, int local, data_t mydata)
{
	int i;
	node_t *p = head;
	node_t *q;

	if (p == NULL)
		return -1;

	/* 判断插入位置是否满足条件：local >= 0 */
	if (local < 1 || local > LengthLinkList(head) + 1)
		return -1;

	/* 找到需要插入结点的前一个结点 */
	for (i = 1; i < local; i++)
	{
		p = p->next;
	}

	/* 创建需要插入数据结点空间 */
	q = malloc(sizeof(node_t));
	if (q == NULL)
		return -1;
	memset(q, 0, sizeof(node_t));
	q->data = mydata;

	/* 插入结点 */
	q->next = p->next;
	p->next = q;

	return 0;
}

void DisplayLinkList(node_t *head)
{
	node_t *p = head->next;

	while (p != NULL)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

int DeleteLinkList(node_t *head, int local)
{
	int i;
	node_t *p = head;
	node_t *q;

	/* 判断链表是否为空表：空表删除失败 */
	if (head->next == NULL)
		return -1;

	/* 找要删除结点的前一个结点 */
	for (i = 0; i < local && p->next != NULL; i++)
		p = p->next;
	if (p->next == NULL)
		return -1;

	/* 删除结点 */
	q = p->next;
	p->next = q->next;
	free(q);

	return 0;
}

int SelectLinkList(node_t *head, int local, data_t *mydata)
{
	int i;
	node_t *p;

	/* 判断链表是否为空表 */
	if (head->next == NULL)
		return -1;

	/* 查找到指定序号的结点 */
	p = head->next;
	for (i = 0; i < local && p != NULL; i++)
		p = p->next;
	if (p == NULL)
		return -1;
	/* 返回结点的数据信息 */
	*mydata = p->data;

	return 0;
}

int UpdateLinkList(node_t *head, int local, data_t newdata)
{
	int i;
	node_t *p;

	/* 判断链表是否为空表 */
	if (head->next == NULL)
		return -1;

	/* 查找到指定序号的结点 */
	p = head->next;
	for (i = 0; i < local && p != NULL; i++)
		p = p->next;
	if (p == NULL)
		return -1;

	/* 修改结点的数据域 */
	p->data = newdata;

	return 0;
}

/* 判断链表是否为空表 */
int isEmptyLinkList(node_t *head)
{
	return (head->next == NULL);
}

/* 判断链表是否为满表 */
int isFullLinkList(node_t *head)
{
	return 0; /* 链表不可能为满表，返回0表示false */
}

/* 计算链表中有效数据结点个数，链表的长度 */
int LengthLinkList(node_t *head)
{
	int len = 0;
	node_t *p = head->next;

	while (p != NULL)
	{
		len++;
		p = p->next;
	}
	return len;
}

/* 清空链表的数据结点，头结点保留 */
void ClearLinkList(node_t *head)
{
	node_t *q;
	node_t *p = head->next;
	head->next = NULL;

	while (p != NULL)
	{
		q = p;
		p = p->next;
		free(q);
	}
}

/* 销毁整个链表 */
void DestoryLinkList(node_t **head)
{
	node_t *q;
	node_t *p = *head;
	*head = NULL;

	while (p != NULL)
	{
		q = p;
		p = p->next;
		free(q);
	}
}

void ReverseLinkList(node_t *head)
{
	node_t *q;
	node_t *p = head->next; /* p是用来遍历整个链表中的有效数据结点 */
	head->next = NULL;		/* 头结点的指针域设置为NULL */

	/* 实现倒序运算处理 */
	while (p != NULL)
	{
		q = p;		 /* 遍历到的结点p赋值给运算结点q */
		p = p->next; /* 遍历到下一个结点p */
		/* 头部插入：实现后遍历到的结点插入到先遍历到的结点之前 */
		q->next = head->next;
		head->next = q;
	}
}

void SortLinkList(node_t *head)
{
	node_t *p;
	node_t *q;
	node_t *r;

	if (head->next == NULL)
		return;

	p = head->next->next; /* 第0个有效数据结点作为有效序列，从第1个有效数据结点开始做顺序插入排序 */
	head->next->next = NULL;

	while (p != NULL)
	{
		q = p;		 /* 遍历需要排序的结点p赋值给运算结点q */
		p = p->next; /* 遍历到下一个结点 */

		/* 循环找到需要插入结点位置的前一个结点 */
		r = head;
		while (r->next != NULL)
		{								 /* r的下一个结点是否存在，r->next == NULL说明r为有效链表的最后一个结点 */
			if (r->next->data > q->data) /* 下一个结点数据 > 大于插入结点的数据，说明当前结点为插入结点大的前一个结点 */
				break;
			r = r->next;
		}
		/* 在r结点后插入待排序结点q */
		q->next = r->next;
		r->next = q;
	}
}

node_t *MergeLinkList(node_t **head1, node_t **head2)
{
	node_t *t;
	node_t *r;
	node_t *p = (*head1)->next; /* 指针p遍历链表head1的所有有序数据结点 */
	node_t *q = (*head2)->next; /* 指针q遍历链表head2的所有有序数据结点 */
	(*head1)->next = NULL;
	t = *head1;	  /* 链表head1的头结点作为新的链表头结点，未操作的时候是新的链表的尾结点 */
	free(*head2); /* 释放链表head2的头结点，将链表head1的头结点作为新的链表头结点 */
	*head2 = NULL;

	/* 循环遍历两个链表中结点，其中的一个链表结束，则循环结束 */
	while (p != NULL && q != NULL)
	{
		/* 找到数据较小的结点，赋值给值r进行运算(尾部插入结点) */
		if (p->data > q->data)
		{
			r = q;
			q = q->next;
		}
		else
		{
			r = p;
			p = p->next;
		}
		/* 尾部插入运算:将结点r插入的尾结点t的后面 */
		r->next = t->next; // r->next = NULL;
		t->next = r;
		t = t->next;
	}
	/* 尾部处理 */
	if (p == NULL)
	{
		t->next = q;
	}
	else
	{
		t->next = p;
	}

	return (*head1);
}